001 /*
002 * OutMatrix.java
003 *
004 * Copyright 2003 Sergio Anibal de Carvalho Junior
005 *
006 * This file is part of NeoBio.
007 *
008 * NeoBio is free software; you can redistribute it and/or modify it under the terms of
009 * the GNU General Public License as published by the Free Software Foundation; either
010 * version 2 of the License, or (at your option) any later version.
011 *
012 * NeoBio is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
014 * PURPOSE. See the GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License along with NeoBio;
017 * if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
018 * Boston, MA 02111-1307, USA.
019 *
020 * Proper attribution of the author as the source of the software would be appreciated.
021 *
022 * Sergio Anibal de Carvalho Junior mailto:sergioanibaljr@users.sourceforge.net
023 * Department of Computer Science http://www.dcs.kcl.ac.uk
024 * King's College London, UK http://www.kcl.ac.uk
025 *
026 * Please visit http://neobio.sourceforge.net
027 *
028 * This project was supervised by Professor Maxime Crochemore.
029 *
030 */
031
032 package neobio.alignment;
033
034 /**
035 * Implements an interface to the OUT matrix of a block. This class is used by the
036 * {@linkplain CrochemoreLandauZivUkelson} and subclasses to enconde the OUT matrix
037 * from the input border and DIST matrix of an {@linkplain AlignmentBlock}.
038 *
039 * <P>The OUT matrix defined as <CODE>OUT[i,j] = I[i] + DIST[i,j]</CODE> where I is the
040 * input border array and DIST is the DIST matrix.</P>
041 *
042 * <P>The output border of a block is computed from the OUT matrix by taking the maximum
043 * value of each column. Note that this class <B>does not compute the OUT matrix</B>, it
044 * just stores the necessary information to retrieve a value at any position of the
045 * matrix.</P>
046 *
047 * <P>It implements the Matrix interface so that the SMAWK algorithm can be used to
048 * compute its column maxima.</P>
049 *
050 * <P>For more information on how this class is used, please refer to the specification
051 * of the <CODE>CrochemoreLandauZivUkelson</CODE> and its subclasses.
052 *
053 * @author Sergio A. de Carvalho Jr.
054 * @see CrochemoreLandauZivUkelson
055 * @see CrochemoreLandauZivUkelsonGlobalAlignment
056 * @see CrochemoreLandauZivUkelsonLocalAlignment
057 * @see AlignmentBlock
058 * @see Smawk
059 */
060 public class OutMatrix implements Matrix
061 {
062 /**
063 * The length of the longest sequence (number of characters) being aligned. It needs
064 * to be set only once per alignment.
065 */
066 protected int max_length;
067
068 /**
069 * The maximum absolute score that the current scoring scheme can return. It needs
070 * to be set only once per alignment.
071 */
072 protected int max_score;
073
074 /**
075 * The DIST matrix of a block.
076 */
077 protected int[][] dist;
078
079 /**
080 * The input border of a block.
081 */
082 protected int[] input_border;
083
084 /**
085 * The dimension of the OUT matrix.
086 */
087 protected int dim;
088
089 /**
090 * The number of columns of the block.
091 */
092 protected int lc;
093
094 /**
095 * Initialised this OUT matrix interface. This method needs to be executed only once
096 * per alignment.
097 *
098 * @param max_length the length of the longest sequence (number of characters) being
099 * aligned
100 * @param max_score the maximum absolute score that the current scoring scheme can
101 * return
102 */
103 public void init (int max_length, int max_score)
104 {
105 this.max_length = max_length;
106 this.max_score = max_score;
107 }
108
109 /**
110 * Sets this interface's data to represent an OUT matrix for a block. This method
111 * is typically executed once for each block being aligned.
112 *
113 * @param dist the DIST matrix
114 * @param input_border the input border
115 * @param dim the dimension of the OUT matrix
116 * @param lc the number of columns of the block
117 */
118 public void setData (int[][] dist, int[] input_border, int dim, int lc)
119 {
120 this.dist = dist;
121 this.input_border = input_border;
122 this.dim = dim;
123 this.lc = lc;
124 }
125
126 /**
127 * Returns the value at a given position of the matrix. In general it returns the
128 * value of <CODE>DIST[col][row] + input_border[row]</CODE>. However, special cases
129 * occur for its upper right and lower left triangular parts.
130 *
131 * @param row row index
132 * @param col column index
133 * @return the value at row <CODE>row</CODE>, column <CODE>col</CODE> of this OUT
134 * matrix
135 */
136 public int valueAt (int row, int col)
137 {
138 // The DIST matrix is indexed by [column][row]
139
140 if (col < lc)
141 {
142 if (row < dim - (lc - col))
143 return dist[col][row] + input_border[row];
144 else
145 // lower left triangle entries
146 return - (max_length + row + 1) * max_score;
147 }
148 else if (col == lc)
149 {
150 return dist[col][row] + input_border[row];
151 }
152 else
153 {
154 if (row < (col - lc))
155 // upper right triangle entries
156 return Integer.MIN_VALUE + row;
157 else
158 return dist[col][row - (col - lc)] + input_border[row];
159 }
160 }
161
162 /**
163 * Returns the number of rows of this OUT matrix.
164 *
165 * @return the number of rows of this OUT matrix
166 */
167 public int numRows ()
168 {
169 return dim;
170 }
171
172 /**
173 * Returns the number of columns of this OUT matrix.
174 *
175 * @return the number of columns of this OUT matrix
176 */
177 public int numColumns ()
178 {
179 return dim;
180 }
181 }